{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Couples Holding Hands"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #depth-first-search #breadth-first-search #union-find #graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #深度优先搜索 #广度优先搜索 #并查集 #图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minSwapsCouples"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #情侣牵手"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p><code>n</code> 对情侣坐在连续排列的 <code>2n</code>&nbsp;个座位上，想要牵到对方的手。</p>\n",
    "\n",
    "<p>人和座位由一个整数数组 <code>row</code> 表示，其中 <code>row[i]</code> 是坐在第 <code>i </code>个座位上的人的 <strong>ID</strong>。情侣们按顺序编号，第一对是&nbsp;<code>(0, 1)</code>，第二对是&nbsp;<code>(2, 3)</code>，以此类推，最后一对是&nbsp;<code>(2n-2, 2n-1)</code>。</p>\n",
    "\n",
    "<p>返回 <em>最少交换座位的次数，以便每对情侣可以并肩坐在一起</em>。 <i>每次</i>交换可选择任意两人，让他们站起来交换座位。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> row = [0,2,1,3]\n",
    "<strong>输出:</strong> 1\n",
    "<strong>解释:</strong> 只需要交换row[1]和row[2]的位置即可。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> row = [3,2,0,1]\n",
    "<strong>输出:</strong> 0\n",
    "<strong>解释:</strong> 无需交换座位，所有的情侣都已经可以手牵手了。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2n == row.length</code></li>\n",
    "\t<li><code>2 &lt;= n &lt;= 30</code></li>\n",
    "\t<li><code>n</code>&nbsp;是偶数</li>\n",
    "\t<li><code>0 &lt;= row[i] &lt; 2n</code></li>\n",
    "\t<li><code>row</code>&nbsp;中所有元素均<strong>无重复</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [couples-holding-hands](https://leetcode.cn/problems/couples-holding-hands/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [couples-holding-hands](https://leetcode.cn/problems/couples-holding-hands/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[0,2,1,3]', '[3,2,0,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def minSwapsCouples(self, row):\n",
    "        \"\"\"\n",
    "        :type row: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        N = len(row)\n",
    "        res = 0\n",
    "        for i in range(0, N - 1, 2):\n",
    "            if row[i] == row[i + 1] ^ 1:\n",
    "                continue\n",
    "            for j in range(i + 1, N):\n",
    "                if row[i] == row[j] ^ 1:\n",
    "                    row[i + 1], row[j] = row[j], row[i + 1]\n",
    "            res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def minSwapsCouples(self, row):\n",
    "        \"\"\"\n",
    "        :type row: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        N = len(row)\n",
    "        res = 0\n",
    "        for i in range(0, N - 1, 2):\n",
    "            if row[i] == row[i + 1] ^ 1:\n",
    "                continue\n",
    "            for j in range(i + 1, N):\n",
    "                if row[i] == row[j] ^ 1:\n",
    "                    row[i + 1], row[j] = row[j], row[i + 1]\n",
    "            res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        n=len(row)\n",
    "        sets=n//2\n",
    "        father=list(range(sets))\n",
    "        def find(x):\n",
    "            stack=[]\n",
    "            count=0\n",
    "            while father[x]!=x:\n",
    "                stack.append(x)\n",
    "                count+=1\n",
    "                x=father[x]\n",
    "            for i in range(count-1):\n",
    "                father[stack[i]]=x\n",
    "            return x\n",
    "        def unite(x,y):\n",
    "            nonlocal sets\n",
    "            fx=find(x)\n",
    "            fy=find(y)\n",
    "            if fx!=fy:\n",
    "                father[fx]=fy\n",
    "                sets-=1\n",
    "        for i in range(0,n,2):\n",
    "            unite(row[i]//2,row[i+1]//2)\n",
    "        return n//2-sets"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        n = len(row)\n",
    "        self.partent=[i for i in range(0,n//2)]\n",
    "        self.count=n//2\n",
    "        for i in range(0,n,2):\n",
    "            self.union(row[i]//2,row[i+1]//2)\n",
    "        return n//2-self.count\n",
    "\n",
    "    def find(self,x:int)->int:\n",
    "        while x!=self.partent[x]:\n",
    "            self.partent[x]=self.partent[self.partent[x]]\n",
    "            x=self.partent[x]\n",
    "        return x\n",
    "    def union(self,x:int, y:int)->None:\n",
    "        root_x=self.find(x)\n",
    "        root_y=self.find(y)\n",
    "        if root_x==root_y:\n",
    "            return\n",
    "        self.partent[root_x]=root_y\n",
    "        self.count-=1\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        n = len(row) // 2\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            a, b = row[2*i], row[2*i+1]\n",
    "            if a // 2 != b // 2:\n",
    "                # keep A, find its pair\n",
    "                ans += 1\n",
    "                target = a // 2\n",
    "                for j in range(2*i+2, 2*n):\n",
    "                    if row[j] // 2 == target:\n",
    "                        row[2*i+1], row[j] = row[j], row[2*i+1]\n",
    "                        break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        class uni:\n",
    "            def __init__(self,n):\n",
    "                self.N = n\n",
    "                \n",
    "            def find_set(self,x):\n",
    "                if x != s[x]:\n",
    "                    s[x] = self.find_set(s[x])\n",
    "                return s[x]\n",
    "\n",
    "            def merge_set(self,x,y):\n",
    "                x = self.find_set(x)\n",
    "                y = self.find_set(y)\n",
    "                if x != y:\n",
    "                    s[x] = s[y]\n",
    "                else:\n",
    "                    self.N -= 1\n",
    "\n",
    "            def getnum(self):\n",
    "                return self.N\n",
    "\n",
    "        lens = len(row)\n",
    "        s = list(range(lens))\n",
    "        couple = lens//2\n",
    "        mu = uni(couple)\n",
    "        for i in range(0,lens,2):\n",
    "            mu.merge_set(row[i]//2,row[i+1]//2)       \n",
    "        return mu.getnum()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        n = len(row)\n",
    "        tot = n // 2\n",
    "\n",
    "        graph = [[] for _ in range(tot)]\n",
    "        for i in range(0, n, 2):\n",
    "            l = row[i] // 2\n",
    "            r = row[i + 1] // 2\n",
    "            if l != r:\n",
    "                graph[l].append(r)\n",
    "                graph[r].append(l)\n",
    "\n",
    "        visited = [0] * tot\n",
    "        ret = 0\n",
    "\n",
    "        for i in range(tot):\n",
    "            if visited[i] == 0:\n",
    "                q = deque()\n",
    "                visited[i] = 1\n",
    "                q.append(i)\n",
    "                cnt = 0\n",
    "                while q:\n",
    "                    x = q.popleft()\n",
    "                    cnt += 1\n",
    "                    for y in graph[x]:\n",
    "                        if visited[y] == 0:\n",
    "                            visited[y] = 1\n",
    "                            q.append(y)\n",
    "                ret += cnt - 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        n = len(row)\n",
    "        tot = n // 2\n",
    "        g = [[] for _ in range(tot)]\n",
    "        for i in range(0, n, 2):\n",
    "            x, y = row[i] // 2, row[i+1] // 2\n",
    "            if x != y:\n",
    "                g[x].append(y)\n",
    "                g[y].append(x)\n",
    "        ans, visited = 0, [False] * tot\n",
    "        for x in range(tot):\n",
    "            if visited[x]:\n",
    "                continue\n",
    "            q, cnt = deque([x]), 0\n",
    "            visited[x] = True\n",
    "            while q:\n",
    "                t = q.popleft()\n",
    "                for y in g[t]:\n",
    "                    if not visited[y]:\n",
    "                        q.append(y)\n",
    "                        visited[y] = True\n",
    "                        cnt += 1\n",
    "            ans += cnt\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        n = len(row)\n",
    "        d = {}\n",
    "        for i, v in enumerate(row):\n",
    "            d[v] = i\n",
    "        ans = 0\n",
    "        for i in range(0, n - 1, 2):\n",
    "            x = row[i]\n",
    "            if row[i + 1] == (x ^ 1):\n",
    "                continue\n",
    "            y = row[i + 1] # 备份\n",
    "            ans += 1\n",
    "            # x 的伴侣在pos位置上\n",
    "            pos = d[x ^ 1]\n",
    "            row[i + 1], row[pos] = row[pos], row[i + 1]\n",
    "            d[x ^ 1] = i + 1\n",
    "            d[y] = pos\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "\n",
    "        # 遍历列表 先删除所有的已经占好的位置\n",
    "        row = [i//2 for i in row]\n",
    "        for i in range(len(row)//2-1,-1,-1):\n",
    "            if row[i*2] == row[i*2+1]:\n",
    "                del row[i*2:i*2+2]\n",
    "        def find_couple():\n",
    "            return row[1:].index(row[0])+1\n",
    "        \n",
    "        times = 0\n",
    "\n",
    "        while len(row) > 0:\n",
    "            if row[0]!= row[1]:\n",
    "                buffer = find_couple()\n",
    "                row[buffer] = row[1]\n",
    "                times+=1\n",
    "            del row[:2]\n",
    "        return times\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        def find(x: int) -> int:\n",
    "            if p[x] != x:\n",
    "                p[x] = find(p[x])\n",
    "            return p[x]\n",
    "\n",
    "        n = len(row) >> 1\n",
    "        p = list(range(n))\n",
    "        for i in range(0, len(row), 2):\n",
    "            a, b = row[i] >> 1, row[i + 1] >> 1\n",
    "            p[find(a)] = find(b)\n",
    "        return n - sum(i == find(i) for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "\n",
    "        # 遍历列表 先删除所有的已经占好的位置\n",
    "        row = [i//2 for i in row]\n",
    "        for i in range(len(row)//2-1,-1,-1):\n",
    "            if row[i*2] == row[i*2+1]:\n",
    "                del row[i*2:i*2+2]\n",
    "        def find_couple():\n",
    "            return row[1:].index(row[0])+1\n",
    "        \n",
    "        times = 0\n",
    "\n",
    "        while len(row) > 0:\n",
    "            if row[0]!= row[1]:\n",
    "                buffer = find_couple()\n",
    "                row[buffer] = row[1]\n",
    "                times+=1\n",
    "            del row[:2]\n",
    "        return times\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        n = len(row) // 2\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            x = row[2*i]\n",
    "            y = x ^ 1\n",
    "            if row[2*i + 1] != y:\n",
    "                j = row.index(y)\n",
    "                row[2*i+1], row[j] = row[j], row[2*i+1]\n",
    "                ans += 1\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        seat=[-1]*len(row)\n",
    "        for i,x in enumerate(row):\n",
    "            seat[x]=i\n",
    "        ans=0\n",
    "        for i in range(0,len(row),2):\n",
    "            parter=row[i]^1\n",
    "            if parter!=row[i+1]:\n",
    "                j=seat[parter]\n",
    "                row[j]=row[i+1]\n",
    "                seat[row[j]]=j\n",
    "                ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def minSwapsCouples(self, row):\n",
    "        N = len(row)\n",
    "        res = 0\n",
    "        # 题干设定 0与1，2与3。。。配对，因此我们将0与1设置为组0，即0//2 == 1//2 == 0，以此类推\n",
    "        for i in range(0, N - 1, 2):\n",
    "            # 这里的异或十分巧妙，本意是想要检验row[i]与row[i+1]是否仅为最低位不同\n",
    "            if row[i] == row[i + 1] ^ 1:\n",
    "                continue\n",
    "            # 如果不同，则表示该位置上的情侣不配对，因此需要贪心地寻找配对情侣，并使移动次数加1\n",
    "            for j in range(i + 1, N):\n",
    "                if row[i] == row[j] ^ 1:\n",
    "                    row[i + 1], row[j] = row[j], row[i + 1]\n",
    "            res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        ans=0\n",
    "        n = len(row)\n",
    "        for i in range(0,n,2):\n",
    "            if row[i]^1 != row[i+1]:\n",
    "                a= row[i]^1\n",
    "                for j in range(i+1,n):\n",
    "                    if a == row[j]:\n",
    "                        row[i+1],row[j]=row[j],row[i+1]\n",
    "                        ans+=1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        count = 0\n",
    "        for i in range(0, len(row), 2):\n",
    "            if row[i] // 2 == row[i + 1] // 2:\n",
    "                continue\n",
    "            else:\n",
    "                for j in range(i + 2, len(row)):\n",
    "                    if row[j] // 2 == row[i] // 2:\n",
    "                        temp = row[i + 1]\n",
    "                        row[i + 1] = row[j]\n",
    "                        row[j] = temp\n",
    "                        count += 1\n",
    "                        break\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: list[int]) -> int:\n",
    "        wei = [0] * len(row)\n",
    "        n = len(row)\n",
    "        for index, i in enumerate(row):\n",
    "            wei[i] = index\n",
    "        ans = 0\n",
    "        for i in range(0, n, 2):\n",
    "            if row[i] == row[i + 1] ^ 1:\n",
    "                continue\n",
    "            index = wei[row[i] ^ 1]\n",
    "            row[index] = row[i + 1]\n",
    "            wei[row[i + 1]] = index\n",
    "            row[i + 1] = row[i] ^ 1\n",
    "            wei[row[i] ^ 1] = i+1\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        def find(x: int) -> int:\n",
    "            if p[x] != x:\n",
    "                p[x] = find(p[x])\n",
    "            return p[x]\n",
    "\n",
    "        n = len(row) >> 1\n",
    "        p = list(range(n))\n",
    "        for i in range(0, len(row), 2):\n",
    "            a, b = row[i] >> 1, row[i + 1] >> 1\n",
    "            p[find(a)] = find(b)\n",
    "        return n - sum(i == find(i) for i in range(n))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getf(self, f, x):\n",
    "        if f[x] == x:\n",
    "            return x\n",
    "        newf = self.getf(f, f[x])\n",
    "        f[x] = newf\n",
    "        return newf\n",
    "\n",
    "    def add(self, f, x, y):\n",
    "        fx = self.getf(f, x)\n",
    "        fy = self.getf(f, y)\n",
    "        f[fx] = fy\n",
    "\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        n = len(row)\n",
    "        tot = n // 2\n",
    "        f = [i for i in range(tot)]\n",
    "\n",
    "        for i in range(0, n, 2):\n",
    "            l = row[i] // 2\n",
    "            r = row[i + 1] // 2\n",
    "            self.add(f, l, r)\n",
    "\n",
    "        m = {}\n",
    "        for i in range(tot):\n",
    "            fx = self.getf(f, i)\n",
    "            if fx in m:\n",
    "                m[fx] += 1\n",
    "            else:\n",
    "                m[fx] = 1\n",
    "\n",
    "        ret = 0\n",
    "        for f, sz in m.items():\n",
    "            ret += sz - 1\n",
    "\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "\n",
    "        # 遍历列表 先删除所有的已经占好的位置\n",
    "        # \n",
    "        row = [i//2 for i in row]\n",
    "        for i in range(len(row)//2-1,-1,-1):\n",
    "            if row[i*2] == row[i*2+1]:\n",
    "                del row[i*2:i*2+2]\n",
    "        def find_couple():\n",
    "            return row[1:].index(row[0])+1\n",
    "        \n",
    "        times = 0\n",
    "\n",
    "        while len(row) > 0:\n",
    "            if row[0]!= row[1]:\n",
    "                buffer = find_couple()\n",
    "                row[buffer] = row[1]\n",
    "                times+=1\n",
    "            del row[:2]\n",
    "        return times\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: list[int]) -> int:\n",
    "        wei = [0] * len(row)\n",
    "        n = len(row)\n",
    "        for index, i in enumerate(row):\n",
    "            wei[i] = index\n",
    "        ans = 0\n",
    "        for i in range(0, n, 2):\n",
    "            if row[i] == row[i + 1] ^ 1:\n",
    "                continue\n",
    "            index = wei[row[i] ^ 1]\n",
    "            row[index] = row[i + 1]\n",
    "            wei[row[i + 1]] = index\n",
    "            row[i + 1] = row[i] ^ 1\n",
    "            wei[row[i] ^ 1] = i+1\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        n = len(row)\n",
    "        tot = n // 2\n",
    "\n",
    "        graph = [[] for _ in range(tot)]\n",
    "        for i in range(0, n, 2):\n",
    "            l = row[i] // 2\n",
    "            r = row[i + 1] // 2\n",
    "            if l != r:\n",
    "                graph[l].append(r)\n",
    "                graph[r].append(l)\n",
    "\n",
    "        visited = [0] * tot\n",
    "        ret = 0\n",
    "\n",
    "        for i in range(tot):\n",
    "            if visited[i] == 0:\n",
    "                q = deque()\n",
    "                visited[i] = 1\n",
    "                q.append(i)\n",
    "                cnt = 0\n",
    "                while q:\n",
    "                    x = q.popleft()\n",
    "                    cnt += 1\n",
    "                    for y in graph[x]:\n",
    "                        if visited[y] == 0:\n",
    "                            visited[y] = 1\n",
    "                            q.append(y)\n",
    "                ret += cnt - 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getf(self, f, x):\n",
    "        if f[x] == x:\n",
    "            return x\n",
    "        newf = self.getf(f, f[x])\n",
    "        f[x] = newf\n",
    "        return newf\n",
    "\n",
    "    def add(self, f, x, y):\n",
    "        fx = self.getf(f, x)\n",
    "        fy = self.getf(f, y)\n",
    "        f[fx] = fy\n",
    "\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        n = len(row)\n",
    "        tot = n // 2\n",
    "        f = [i for i in range(tot)]\n",
    "\n",
    "        for i in range(0, n, 2):\n",
    "            l = row[i] // 2\n",
    "            r = row[i + 1] // 2\n",
    "            self.add(f, l, r)\n",
    "\n",
    "        m = {}\n",
    "        for i in range(tot):\n",
    "            fx = self.getf(f, i)\n",
    "            if fx in m:\n",
    "                m[fx] += 1\n",
    "            else:\n",
    "                m[fx] = 1\n",
    "\n",
    "        ret = 0\n",
    "        for f, sz in m.items():\n",
    "            ret += sz - 1\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        n=len(row)\n",
    "\n",
    "        def matching(num_list,left,right)-> int:\n",
    "            count=0\n",
    "            for i in range(left+1,right+1,2):\n",
    "                if (num_list[i]%2 and num_list[i]-1==num_list[i-1]) or (num_list[i]%2==0 and num_list[i]+1==num_list[i-1]):\n",
    "                    continue\n",
    "                else:\n",
    "                    target= num_list[i-1]-1 if num_list[i-1]%2 else num_list[i-1]+1\n",
    "                    for j in range(i+1,right+1):\n",
    "                        if num_list[j]==target:\n",
    "                            num_list[j] =num_list[i]\n",
    "                            num_list[i]=target\n",
    "                            break\n",
    "                    count=1+matching(num_list,i+1,right)\n",
    "                    break\n",
    "            return count\n",
    "\n",
    "        count=matching(row,0,n-1)       \n",
    "        return count\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row):\n",
    "        n = len(row)\n",
    "        self.build(n // 2)\n",
    "        for i in range(0, n, 2):\n",
    "            self.union(row[i] // 2, row[i + 1] // 2)\n",
    "        return n // 2 - self.sets\n",
    "\n",
    "    MAXN = 31\n",
    "\n",
    "    def build(self, m):\n",
    "        self.father = [i for i in range(m)]\n",
    "        self.sets = m\n",
    "\n",
    "    def find(self, i):\n",
    "        if i != self.father[i]:\n",
    "            self.father[i] = self.find(self.father[i])\n",
    "        return self.father[i]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        fx = self.find(x)\n",
    "        fy = self.find(y)\n",
    "        if fx != fy:\n",
    "            self.father[fx] = fy\n",
    "            self.sets -= 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        def find(x):\n",
    "            if p[x] != x:\n",
    "                p[x] =find(p[x])\n",
    "            return p[x]\n",
    "        def union(a, b):\n",
    "            p[find(a)] = find(b)\n",
    "\n",
    "        n = len(row) // 2\n",
    "        p = list(range(n))\n",
    "        for i in range(0, len(row), 2):\n",
    "            a, b = row[i] // 2, row[i+1] // 2\n",
    "            union(a, b)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if i != p[i]:\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        def find(x):\n",
    "            if p[x] != x:\n",
    "                p[x] =find(p[x])\n",
    "            return p[x]\n",
    "        def union(a, b):\n",
    "            p[find(a)] = find(b)\n",
    "\n",
    "        n = len(row) // 2\n",
    "        p = list(range(n))\n",
    "        for i in range(0, len(row), 2):\n",
    "            a, b = row[i] // 2, row[i+1] // 2\n",
    "            union(a, b)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if i != p[i]:\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        n = len(row) // 2\n",
    "        h = dict()\n",
    "        ans = 0\n",
    "        anoth = lambda x: x - 1 if x % 2 else x + 1\n",
    "        for i in range(n):\n",
    "            n0, n1 = 2 * i, 2 * i + 1\n",
    "            a, b = row[n0], row[n1]\n",
    "            c = anoth(a)\n",
    "            if b == c:\n",
    "                continue\n",
    "            if c in h:\n",
    "                ans += 1\n",
    "                d = row[anoth(h[c])]\n",
    "                if d == anoth(b):\n",
    "                    h.pop(d)\n",
    "                    h.pop(c)\n",
    "                    continue\n",
    "                else:\n",
    "                    # 将 a 与 d 对调\n",
    "                    a = d\n",
    "                    row[n0] = d\n",
    "                    h[d] = n0\n",
    "                    h[b] = n1\n",
    "                    h.pop(c)\n",
    "            else:\n",
    "                h[a] = n0\n",
    "            if (d := anoth(b)) in h:\n",
    "                ans += 1\n",
    "                c = row[anoth(h[d])]\n",
    "                # 将 b 与 c 对调\n",
    "                row[n1] = c\n",
    "                h[c] = n1\n",
    "                h.pop(d)\n",
    "                h[a] = n0\n",
    "            else:\n",
    "                h[b] = n1\n",
    "        # print(h, row)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(0,len(row)-1,2):\n",
    "            x = row[i]\n",
    "            if row[i+1]== x^1:\n",
    "                continue\n",
    "            ans += 1\n",
    "            for j in range(i+1,len(row)):\n",
    "                if row[j] == x^1:\n",
    "                    row[i+1] , row[j] = row[j], row[i+1]\n",
    "                    break\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        def find(x: int) -> int:\n",
    "            if p[x] != x:\n",
    "                p[x] = find(p[x])\n",
    "            return p[x]\n",
    "\n",
    "        n = len(row) >> 1\n",
    "        p = list(range(n))\n",
    "        for i in range(0, len(row), 2):\n",
    "            a, b = row[i] >> 1, row[i + 1] >> 1\n",
    "            p[find(a)] = find(b)\n",
    "        return n - sum(i == find(i) for i in range(n))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(0,len(row)-1,2):\n",
    "            x = row[i]\n",
    "            if row[i+1]== x^1:\n",
    "                continue\n",
    "            ans += 1\n",
    "            for j in range(i+1,len(row)):\n",
    "                if row[j] == x^1:\n",
    "                    row[i+1] , row[j] = row[j], row[i+1]\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        def is_couple(i,j):\n",
    "            return (i//2)==(j//2)\n",
    "        \n",
    "        def count_couple_number():\n",
    "            count = 0\n",
    "            for i in range(0,len(row),2):\n",
    "                if is_couple(row[i],row[i+1]):\n",
    "                    count += 1\n",
    "            return count\n",
    "        \n",
    "        count = 0\n",
    "        while count_couple_number()<len(row)//2:\n",
    "            for i in range(0,len(row),2):\n",
    "                if not is_couple(row[i],row[i+1]):\n",
    "                    for j in range(i+2,len(row)):\n",
    "                        if is_couple(row[i],row[j]):\n",
    "                            row[i+1],row[j] = row[j],row[i+1]\n",
    "                            count += 1\n",
    "        return count\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        def find(x: int) -> int:\n",
    "            if p[x] != x:\n",
    "                p[x] = find(p[x])\n",
    "            return p[x]\n",
    "\n",
    "        n = len(row) >> 1\n",
    "        p = list(range(n))\n",
    "        for i in range(0, len(row), 2):\n",
    "            a, b = row[i] >> 1, row[i + 1] >> 1\n",
    "            p[find(a)] = find(b)\n",
    "        return n - sum(i == find(i) for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        n = len(row)\n",
    "        tot = n // 2\n",
    "\n",
    "        # Create an adjacency list (graph) to represent connections between couples\n",
    "        graph = [[] for _ in range(tot)]\n",
    "        for i in range(0, n, 2):\n",
    "            l = row[i] // 2\n",
    "            r = row[i + 1] // 2\n",
    "            if l != r:\n",
    "                graph[l].append(r)\n",
    "                graph[r].append(l)\n",
    "\n",
    "        # Initialize a list to keep track of visited nodes\n",
    "        visited = [0] * tot\n",
    "        ret = 0\n",
    "\n",
    "        # Traverse the graph using Breadth-First Search (BFS)\n",
    "        for i in range(tot):\n",
    "            if visited[i] == 0:\n",
    "                q = deque()\n",
    "                visited[i] = 1\n",
    "                q.append(i)\n",
    "                cnt = 0\n",
    "                while q:\n",
    "                    x = q.popleft()\n",
    "                    cnt += 1\n",
    "                    for y in graph[x]:\n",
    "                        if visited[y] == 0:\n",
    "                            visited[y] = 1\n",
    "                            q.append(y)\n",
    "                ret += cnt - 1\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        pos = [0] * len(row)\n",
    "        for i, e in enumerate(row):\n",
    "            pos[e] = i\n",
    "        \n",
    "        res = 0\n",
    "        get_partner = lambda x: x ^ 1\n",
    "        for i in range(0, len(row) - 1, 2):\n",
    "            partner, j = get_partner(row[i]), i + 1\n",
    "            while row[j] != partner:\n",
    "                partner2 = get_partner(row[j])\n",
    "                pos2 = pos[partner2] ^ 1\n",
    "                pos[row[j]], pos[partner2] = pos[partner2], pos[row[j]]\n",
    "                row[j], row[pos2] = row[pos2], row[j]\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 并查集\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.parent = [i for i in range(n)]\n",
    "    \n",
    "    def find(self, x):\n",
    "        while x != self.parent[x]:\n",
    "            self.parent[x] = self.parent[self.parent[x]]\n",
    "            x = self.parent[x]\n",
    "        return x\n",
    "    \n",
    "    def union(self, x, y):\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "        if root_x == root_y:\n",
    "            return False\n",
    "        self.parent[root_x] = root_y\n",
    "        return True\n",
    "    \n",
    "    def is_connect(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        n = len(row) // 2\n",
    "        row = [i//2 for i in row]\n",
    "        union_find = UnionFind(n)\n",
    "        circle_count = 0\n",
    "\n",
    "        for i in range(0, 2*n, 2):\n",
    "            x = row[i]\n",
    "            y = row[i+1]\n",
    "            if x == y:\n",
    "                circle_count += 1\n",
    "                continue\n",
    "            if not union_find.union(x, y):\n",
    "                circle_count += 1\n",
    "        \n",
    "        return n - circle_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "\n",
    "        l_cop=len(row)\n",
    "        cnt1=0\n",
    "        cnt2=0\n",
    "        row=[s//2 for s in row]\n",
    "        time=0\n",
    "        move=0\n",
    "        while move<l_cop-1:\n",
    "            cur_num=row[move]\n",
    "            if cur_num==row[move+1]:\n",
    "                move+=2\n",
    "                continue\n",
    "            target_index=row.index(cur_num,move+1)\n",
    "            temp=row[move+1]\n",
    "            row[move+1]=cur_num\n",
    "            row[target_index]=temp\n",
    "            move+=2\n",
    "            time+=1\n",
    "        return time\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        pair_n = len(row) // 2\n",
    "        seen = set()\n",
    "        match_pair = {}\n",
    "        for i in range(0, len(row), 2):\n",
    "            match_pair[i] = i + 1\n",
    "            match_pair[i + 1] = i\n",
    "        index_dict = {row[i]:i for i in range(len(row))}\n",
    "        cnt = 0\n",
    "        for i in range(0, len(row), 2):\n",
    "            if row[i] in seen:\n",
    "                continue\n",
    "            if row[i] // 2 == row[i + 1] // 2:\n",
    "                continue\n",
    "            s = row[i]\n",
    "            f = match_pair[row[i]]\n",
    "            index = i + 1\n",
    "            \n",
    "            while(f != row[index]):\n",
    "                seen.add(row[index])\n",
    "                next_val = match_pair[row[index]]\n",
    "                seen.add(next_val)\n",
    "                next_idx = index_dict[next_val]\n",
    "                if next_idx % 2:\n",
    "                    index = next_idx - 1\n",
    "                else:\n",
    "                    index = next_idx + 1\n",
    "                cnt += 1\n",
    "            seen.add(f)\n",
    "        return cnt\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        n=len(row)\n",
    "        d={}\n",
    "        for i in range(n):\n",
    "            d[row[i]]=i\n",
    "        ans=0\n",
    "        # 遍历偶数下标位置\n",
    "        for i in range(0,n,2):\n",
    "            # 如果偶数奇数相邻位置元素不配对\n",
    "            if row[i]//2!=row[i+1]//2:\n",
    "                ans+=1\n",
    "                partner=-1\n",
    "                # 伴侣\n",
    "                if row[i]%2==0:\n",
    "                    partner=row[i]+1\n",
    "                else:\n",
    "                    partner=row[i]-1\n",
    "                #伴侣当前所在位置\n",
    "                ppos=d[partner]\n",
    "                # 小三\n",
    "                san=row[i+1]\n",
    "                # 小三和伴侣互换\n",
    "                row[i+1],row[ppos]= row[ppos],row[i+1]\n",
    "                # 更新伴侣位置为相邻位置\n",
    "                d[partner]=i+1\n",
    "                # 更新小三位置为之前伴侣所在位置\n",
    "                d[san]=ppos\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getf(self, f, x):\n",
    "        if f[x] == x:\n",
    "            return x\n",
    "        newf = self.getf(f, f[x])\n",
    "        f[x] = newf\n",
    "        return newf\n",
    "    \n",
    "    def add(self, f, x, y):\n",
    "        fx = self.getf(f, x)\n",
    "        fy = self.getf(f, y)\n",
    "        f[fx] = fy\n",
    "        # print(\"添加：x=\",x,\"y=\",y,\"fx=\",fx,\"fy=\",fy,\"f:\",f)\n",
    "\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        n = len(row)\n",
    "        tot = n // 2\n",
    "        f = [i for i in range(tot)]\n",
    "\n",
    "        for i in range(0,n,2):\n",
    "            l = row[i] // 2\n",
    "            r = row[i+1] // 2\n",
    "            self.add(f, l, r)\n",
    "\n",
    "        m = {}\n",
    "        for i in range(tot):\n",
    "            fx = self.getf(f, i)\n",
    "            if fx in m:\n",
    "                m[fx] += 1\n",
    "            else:\n",
    "                m[fx] = 1\n",
    "        ret = 0\n",
    "        for c, sz in m.items():\n",
    "            ret += sz - 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        n = len(row) // 2\n",
    "        pos = [-1] * (2 * n)\n",
    "        for i in range(2 * n):\n",
    "            pos[row[i]] = i\n",
    "        visit = [False] * (2 * n)\n",
    "        \n",
    "        def get_half(x): return x - 1 if x % 2 else x + 1\n",
    "\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            if visit[2 * i] == False:\n",
    "                cnt += 1\n",
    "                graph_q = queue.Queue()\n",
    "                graph_q.put((2 * i, row[2 * i]))\n",
    "                visit[i] = True\n",
    "                while not graph_q.empty():\n",
    "                    idx, num = graph_q.get()\n",
    "                    coup_num, neigh_idx = get_half(num), get_half(idx)\n",
    "                    coup_idx, neigh_num = pos[coup_num], row[neigh_idx]\n",
    "                    if not visit[coup_idx]:\n",
    "                        visit[coup_idx] = True\n",
    "                        graph_q.put((coup_idx, coup_num))\n",
    "                    if not visit[neigh_idx]:\n",
    "                        visit[neigh_idx] = True\n",
    "                        graph_q.put((neigh_idx, neigh_num))\n",
    "\n",
    "        return n - cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        n = len(row)\n",
    "        if n == 2: return 0\n",
    "        mp = {}\n",
    "        for i in range(n):\n",
    "            mp[row[i]] = i\n",
    "        hand = 0\n",
    "        steps = 0\n",
    "        while hand < n:\n",
    "            if row[hand]%2 == 0:target = row[hand] + 1\n",
    "            else:target = row[hand] - 1\n",
    "            if mp[target] != hand +1:\n",
    "                steps += 1\n",
    "                a = row[hand+1]\n",
    "                row[hand+1] = row[mp[target]]\n",
    "                row[mp[target]] = a\n",
    "                mp[row[mp[target]]] = mp[target]\n",
    "            hand += 2\n",
    "        return steps\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getf(self, f, x):\n",
    "        if f[x] == x:\n",
    "            return x\n",
    "        newf = self.getf(f, f[x])\n",
    "        f[x] = newf\n",
    "        return newf\n",
    "\n",
    "    def add(self, f, x, y):\n",
    "        fx = self.getf(f, x)\n",
    "        fy = self.getf(f, y)\n",
    "        f[fx] = fy\n",
    "\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        n = len(row)\n",
    "        tot = n // 2\n",
    "        f = [i for i in range(tot)]\n",
    "\n",
    "        for i in range(0, n, 2):\n",
    "            l = row[i] // 2\n",
    "            r = row[i + 1] // 2\n",
    "            self.add(f, l, r)\n",
    "\n",
    "        m = {}\n",
    "        for i in range(tot):\n",
    "            fx = self.getf(f, i)\n",
    "            if fx in m:\n",
    "                m[fx] += 1\n",
    "            else:\n",
    "                m[fx] = 1\n",
    "\n",
    "        ret = 0\n",
    "        for f, sz in m.items():\n",
    "            ret += sz - 1\n",
    "\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 贪心:遇到不匹配的，就寻找匹配的人，交换一次\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        n=len(row)\n",
    "        d={}\n",
    "        for i in range(n):\n",
    "            d[row[i]]=i\n",
    "        ans=0\n",
    "        # 遍历偶数下标位置\n",
    "        for i in range(0,n,2):\n",
    "            # 如果偶数奇数相邻位置元素不配对\n",
    "            if row[i]//2!=row[i+1]//2:\n",
    "                # 交换次数加一\n",
    "                ans+=1\n",
    "                partner=-1\n",
    "                # 与之匹配的伴侣\n",
    "                if row[i]%2==0:\n",
    "                    partner=row[i]+1\n",
    "                else:\n",
    "                    partner=row[i]-1\n",
    "                #伴侣当前所在位置\n",
    "                ppos=d[partner]\n",
    "                # 小三\n",
    "                san=row[i+1]\n",
    "                # 小三和伴侣互换\n",
    "                row[i+1],row[ppos]= row[ppos],row[i+1]\n",
    "                # 更新伴侣位置为相邻位置\n",
    "                d[partner]=i+1\n",
    "                # 更新小三位置为之前伴侣所在位置\n",
    "                d[san]=ppos\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(0, len(row), 2):\n",
    "            x = row[i]\n",
    "            if row[i+1] == x^1: continue\n",
    "            ans += 1\n",
    "            for j in range(i+1, len(row)):\n",
    "                if row[j] == x^1:\n",
    "                    row[i+1], row[j] = row[j], row[i+1]\n",
    "                    break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: list[int]) -> int:\n",
    "        def find(x: int) -> int:\n",
    "            if p[x] != x:\n",
    "                p[x] = find(p[x])\n",
    "            return p[x]\n",
    "\n",
    "        n = len(row) >> 1\n",
    "        p = list(range(n))\n",
    "        for i in range(0, len(row), 2):\n",
    "            a, b = row[i] >> 1, row[i + 1] >> 1\n",
    "            p[find(a)] = find(b)\n",
    "        return n - sum(i == find(i) for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(0, len(row), 2):\n",
    "            x = row[i]\n",
    "            if row[i + 1] == x ^ 1:\n",
    "                continue\n",
    "            ans += 1\n",
    "            for j in range(i + 1, len(row)):\n",
    "                if row[j] == x ^ 1:\n",
    "                    row[i + 1], row[j] = row[j], row[i + 1]\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        # 贪心\n",
    "        n = len(row)\n",
    "        ans = 0\n",
    "        d = dict([v, i] for i, v in enumerate(row))\n",
    "        for i in range(0, n - 1, 2):\n",
    "            if row[i] == row[i + 1] ^ 1:\n",
    "                continue\n",
    "            ans += 1\n",
    "            # 更新字典\n",
    "            d[row[i + 1]] = d[row[i] ^ 1]\n",
    "            row[i + 1], row[d[row[i] ^ 1]] = row[d[row[i] ^ 1]], row[i + 1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.parent = list(range(n))\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        rootX = self.find(x)\n",
    "        rootY = self.find(y)\n",
    "        if rootX != rootY:\n",
    "            self.parent[rootX] = rootY\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        n = len(row) // 2\n",
    "        uf = UnionFind(n)\n",
    "\n",
    "        for i in range(0, len(row), 2):\n",
    "            uf.union(row[i] // 2, row[i + 1] // 2)\n",
    "\n",
    "        return sum(uf.find(i) != i for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        n = len(row)\n",
    "        if n == 2: return 0\n",
    "        mp = {}\n",
    "        for i in range(n):\n",
    "            mp[row[i]] = i\n",
    "        hand = 0\n",
    "        steps = 0\n",
    "        while hand < n:\n",
    "            if row[hand]%2 == 0:target = row[hand] + 1\n",
    "            else:target = row[hand] - 1\n",
    "            if mp[target] != hand +1:\n",
    "                steps += 1\n",
    "                a = row[hand+1]\n",
    "                row[hand+1] = row[mp[target]]\n",
    "                row[mp[target]] = a\n",
    "                mp[row[mp[target]]] = mp[target]\n",
    "            hand += 2\n",
    "        return steps\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getf(self, f, x):\n",
    "        if f[x] == x:\n",
    "            return x\n",
    "        newf = self.getf(f, f[x])\n",
    "        f[x] = newf\n",
    "        return newf\n",
    "\n",
    "    def add(self, f, x, y):\n",
    "        fx = self.getf(f, x)\n",
    "        fy = self.getf(f, y)\n",
    "        f[fx] = fy\n",
    "\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        n = len(row)\n",
    "        tot = n // 2\n",
    "        f = [i for i in range(tot)]\n",
    "\n",
    "        for i in range(0, n, 2):\n",
    "            l = row[i] // 2\n",
    "            r = row[i + 1] // 2\n",
    "            self.add(f, l, r)\n",
    "\n",
    "        m = {}\n",
    "        for i in range(tot):\n",
    "            fx = self.getf(f, i)\n",
    "            if fx in m:\n",
    "                m[fx] += 1\n",
    "            else:\n",
    "                m[fx] = 1\n",
    "\n",
    "        ret = 0\n",
    "        for f, sz in m.items():\n",
    "            ret += sz - 1\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getf(self, f, x):\n",
    "        if f[x] == x:\n",
    "            # 如果找到了，就返回\n",
    "            return x\n",
    "        # 找到的不一样时，就先将当前置为返回值，然后返回返回值\n",
    "        # 为什么要这么做？\n",
    "        # 学到了，是路径压缩\n",
    "        newf = self.getf(f, f[x])\n",
    "        f[x] = newf\n",
    "        return newf\n",
    "\n",
    "    def add(self, f, x, y):\n",
    "        fx = self.getf(f, x)\n",
    "        fy = self.getf(f, y)\n",
    "        f[fx] = fy\n",
    "\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        n = len(row)\n",
    "        tot = n // 2\n",
    "        f = [i for i in range(tot)]\n",
    "\n",
    "        for i in range(0, n, 2):\n",
    "            l = row[i] // 2\n",
    "            r = row[i + 1] // 2\n",
    "            self.add(f, l, r)\n",
    "        \n",
    "        m = [0]*tot\n",
    "        for i in range(tot):\n",
    "            fx = self.getf(f, i)\n",
    "    \n",
    "            m[fx] += 1\n",
    "        # print(m)\n",
    "        ret = 0\n",
    "        for  sz in m:\n",
    "            if sz==0:\n",
    "                continue\n",
    "            ret += sz - 1\n",
    "\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getf(self, f, x):\n",
    "        if f[x] == x:\n",
    "            return x\n",
    "        newf = self.getf(f, f[x])\n",
    "        f[x] = newf\n",
    "        return newf\n",
    "\n",
    "    def add(self, f, x, y):\n",
    "        fx = self.getf(f, x)\n",
    "        fy = self.getf(f, y)\n",
    "        f[fx] = fy\n",
    "\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        n = len(row)\n",
    "        tot = n // 2\n",
    "        f = [i for i in range(tot)]\n",
    "\n",
    "        for i in range(0, n, 2):\n",
    "            l = row[i] // 2\n",
    "            r = row[i + 1] // 2\n",
    "            self.add(f, l, r)\n",
    "\n",
    "        m = {}\n",
    "        for i in range(tot):\n",
    "            fx = self.getf(f, i)\n",
    "            if fx in m:\n",
    "                m[fx] += 1\n",
    "            else:\n",
    "                m[fx] = 1\n",
    "\n",
    "        ret = 0\n",
    "        for f, sz in m.items():\n",
    "            ret += sz - 1\n",
    "\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        n = len(row)\n",
    "        fa = [i for i in range(2 * n)]\n",
    "        cnt = 0\n",
    "        def find(x):\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def union(x, y):\n",
    "            fx, fy = find(x), find(y)\n",
    "            if fx == fy:\n",
    "                return\n",
    "            fa[fy] = fx\n",
    "        \n",
    "        for i in range(0, n, 2):\n",
    "            union(row[i] // 2, row[i + 1] // 2)\n",
    "\n",
    "        for i in range(n // 2):\n",
    "            if find(i) == i:\n",
    "                cnt += 1\n",
    "        return n // 2 - cnt\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        n = len(row)\n",
    "        tot = n // 2\n",
    "\n",
    "        graph = [[] for _ in range(tot)]\n",
    "        for i in range(0, n, 2):\n",
    "            l = row[i] // 2\n",
    "            r = row[i + 1] // 2\n",
    "            if l != r:\n",
    "                graph[l].append(r)\n",
    "                graph[r].append(l)\n",
    "\n",
    "        visited = [0] * tot\n",
    "        ret = 0\n",
    "\n",
    "        for i in range(tot):\n",
    "            if visited[i] == 0:\n",
    "                q = deque()\n",
    "                visited[i] = 1\n",
    "                q.append(i)\n",
    "                cnt = 0\n",
    "                while q:\n",
    "                    x = q.popleft()\n",
    "                    cnt += 1\n",
    "                    for y in graph[x]:\n",
    "                        if visited[y] == 0:\n",
    "                            visited[y] = 1\n",
    "                            q.append(y)\n",
    "                ret += cnt - 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        lens = int(len(row)/2)\n",
    "        d = [i for i in range(lens)]\n",
    "        def find(x):\n",
    "            if d[x]!=x:\n",
    "                x = find(d[x])\n",
    "            return d[x]\n",
    "        for i in range(2*lens):\n",
    "            if i%2==1:\n",
    "                continue\n",
    "            a, b = int(row[i]/2), int(row[i+1]/2)\n",
    "            d[find(a)] = find(b)\n",
    "        \n",
    "        return lens-sum([i==d[i] for i in range(lens)])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class DisjointSet:\n",
    "    def __init__(self, n):\n",
    "        self.parent = [i for i in range(n)]  # 存储每个元素的父节点\n",
    "        self.count = n\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])  # 路径压缩，将x的父节点设为根节点\n",
    "        return self.parent[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "        if root_x != root_y:\n",
    "            self.parent[root_x] = root_y\n",
    "            self.count -= 1\n",
    "\n",
    "    def connected(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "    def get_count(self):\n",
    "        return self.count\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        n = len(row)\n",
    "        N = n // 2\n",
    "        d = DisjointSet(N)\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            d.union(row[i] // 2, row[i + 1] // 2)\n",
    "            i += 2\n",
    "        return N - d.get_count()\n",
    "\n",
    "    def minSwapsCouples2(self, row: List[int]) -> int:\n",
    "        n = len(row)\n",
    "        N = len(row) // 2\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if row[i] // 2 != row[i + 1] // 2:\n",
    "                ans += 1\n",
    "            i += 2\n",
    "        if ans == 0:\n",
    "            return 0\n",
    "        return ans - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def __init__(self):\n",
    "    #     self.p = [i for i in range(70)]\n",
    "\n",
    "    # def union(self, a, b):\n",
    "    #     self.p[self.find(a)] = self.p[self.find(b)]\n",
    "\n",
    "    # def find(self, x):\n",
    "    #     if self.p[x] != x:\n",
    "    #         self.p[x] = self.find(self.p[x])\n",
    "    #     return self.p[x]\n",
    "\n",
    "    # def minSwapsCouples(self, row):\n",
    "    #     n = len(row)\n",
    "    #     m = n // 2\n",
    "    #     for i in range(0,n,2):\n",
    "    #         self.union(row[i] // 2, row[i + 1] // 2)\n",
    "    #     cnt = 0\n",
    "    #     for i in range(m):\n",
    "    #         if i == self.find(i):\n",
    "    #             cnt += 1\n",
    "    #     return m - cnt\n",
    "\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "\n",
    "        def union(a: int, b: int):\n",
    "            p[find(a)] = p[find(b)]\n",
    "        \n",
    "        def find(x):\n",
    "            if(p[x] != x): p[x] = find(p[x])\n",
    "            return p[x]\n",
    "        \n",
    "        n = len(row)\n",
    "        m = n // 2\n",
    "\n",
    "        p = [i for i in range(m)]\n",
    "        for i in range(0, n, 2):\n",
    "            union(row[i] // 2, row[i + 1]//2)\n",
    "\n",
    "        cnt = 0\n",
    "        for i in range(m):\n",
    "            if i == find(i):\n",
    "                cnt += 1\n",
    "        \n",
    "        return m - cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        num = 0\n",
    "        while row:\n",
    "            for i in range(len(row)):\n",
    "                if row[0] // 2 == row[1] // 2:      # 相同直接拿出\n",
    "                    del row[0]\n",
    "                    del row[0]\n",
    "                    if row == []:\n",
    "                        break\n",
    "                    continue\n",
    "                for j in range(len(row)):\n",
    "                    if row[j] // 2 == row[0] // 2 and j != 0:\n",
    "                        row[j],row[1] = row[1],row[j]\n",
    "                        num += 1\n",
    "                        break\n",
    "        return num\n",
    "                    \n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        n = len(row) // 2\n",
    "        fa = [i for i in range(n)]\n",
    "\n",
    "        def find(x):\n",
    "            if fa[x] == x:\n",
    "                return fa[x]\n",
    "            else:\n",
    "                fa[x] = find(fa[x])\n",
    "                return fa[x]\n",
    "\n",
    "        for i in range(n):\n",
    "            l = find(row[i*2] // 2)\n",
    "            r = find(row[i*2 + 1] // 2)\n",
    "            fa[r] = l\n",
    "        \n",
    "        cnt = [0 for i in range(n)]\n",
    "        for i in range(n):\n",
    "            cnt[find(i)] += 1\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if cnt[i] > 0:\n",
    "                ans += cnt[i] - 1\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        num = 0\n",
    "        while row:\n",
    "            for i in range(len(row)):\n",
    "                if row[0] // 2 == row[1] // 2:      # 相同直接拿出\n",
    "                    del row[0]\n",
    "                    del row[0]\n",
    "                    if row == []:\n",
    "                        break\n",
    "                    continue\n",
    "                for j in range(len(row)):\n",
    "                    if row[j] // 2 == row[0] // 2 and j != 0:\n",
    "                        row[j],row[1] = row[1],row[j]\n",
    "                        num += 1\n",
    "                        break\n",
    "        return num\n",
    "                    \n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        N=len(row)//2\n",
    "\n",
    "        qls=[[] for _ in range(N)]\n",
    "        for i,x in enumerate(row):\n",
    "            qls[x//2].append(i//2)\n",
    "        adj = [[] for _ in range(N)]\n",
    "        for x, y in qls:\n",
    "            adj[x].append(y)\n",
    "            adj[y].append(x)\n",
    "        ans = N\n",
    "        for start in range(N):\n",
    "            if not adj[start]: continue\n",
    "            ans -= 1\n",
    "            x, y = start, adj[start].pop()\n",
    "            while y != start:\n",
    "                adj[y].remove(x)\n",
    "                x, y = y, adj[y].pop()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        # 建图就可以了 看能分几波\n",
    "        n = len(row) // 2\n",
    "        dic = defaultdict(set)\n",
    "        for i in range(n):\n",
    "            n1 = row[2*i] // 2\n",
    "            n2 = row[2*i+1] // 2\n",
    "            if n1 != n2:\n",
    "                dic[n1].add(n2)\n",
    "                dic[n2].add(n1)\n",
    "        \n",
    "        visited = set()\n",
    "        ans = 0\n",
    "        for k in dic.keys():\n",
    "            if k not in visited:\n",
    "                tmp = 1\n",
    "                visited.add(k)\n",
    "                lis = [k]\n",
    "                while lis:\n",
    "                    kk = lis.pop()\n",
    "                    for jj in dic[kk]:\n",
    "                        if jj not in visited:\n",
    "                            tmp+=1\n",
    "                            visited.add(jj)\n",
    "                            lis.append(jj)\n",
    "                ans += (tmp -1)\n",
    "\n",
    "        return ans\n",
    "            \n",
    "                \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        num = 0\n",
    "        while row:\n",
    "            for i in range(len(row) // 2):\n",
    "                if row[0] // 2 == row[1] // 2:      # 相同直接拿出\n",
    "                    del row[0]\n",
    "                    del row[0]\n",
    "                    # if row == []:\n",
    "                    #    break\n",
    "                    continue\n",
    "                for j in range(len(row)):\n",
    "                    if row[j] // 2 == row[0] // 2 and j != 0:\n",
    "                        row[j],row[1] = row[1],row[j]\n",
    "                        num += 1\n",
    "                        break\n",
    "        return num\n",
    "                    \n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 分析 + （置换环 / 连通分量）思想 + 并查集\n",
    "# 假设有k对情侣相互之间坐错了位置，那么这k对情侣处于一个置换环中，一个置换环表示内部任意对情侣进行置换也不会完全匹配回原来的情侣，也即一次交换只能还原一对情侣的匹配情况，所以k对情侣需要k-1次交换。那么题目变成查找每个置换环的大小。怎么判断两对情侣在一个置换环中，一个情侣位上相邻的两个人如果不是一对情侣，那么他们代表的情侣对就需要进行交换，就在一个置换环中，可以把每个人的编号除以2表示对应的情侣对编号，这样不断枚举情侣位就可以建立所有情侣对编号的连边关系，连边后求出每个环的大小即可，这种建图后找环大小是BFS做法。还有一种并查集做法，注意到k对情侣对的置换环贡献是k - 1，那么所有置换环的贡献和为Σ(ki - 1) = Σki - 置换环个数，而Σki表示所有环情侣对的总和，即为n / 2，而置换环大小也极为连通分量大小，可以使用并查集计算连通分量大小。\n",
    "# BFS做法（先建图再求每个环大小）\n",
    "\n",
    "class Solution:\n",
    "    def minSwapsCouples(self, row: List[int]) -> int:\n",
    "        n = len(row)\n",
    "        g = [[] for _ in range(n // 2)]\n",
    "        for i in range(0, n, 2):\n",
    "            l, r = row[i] // 2, row[i + 1]//2\n",
    "            if l != r:\n",
    "                g[l].append(r)\n",
    "                g[r].append(l)\n",
    "        vis = [False] * (n//2)\n",
    "        ans = 0\n",
    "        for i in range(n//2):\n",
    "            if not vis[i]:\n",
    "                vis[i] = True\n",
    "                cnt = 1\n",
    "                q = [i]\n",
    "                while q:\n",
    "                    nq = q\n",
    "                    q = []\n",
    "                    for x in nq:\n",
    "                        for y in g[x]:\n",
    "                            if not vis[y]:\n",
    "                                vis[y] = True\n",
    "                                cnt += 1\n",
    "                                q .append(y)\n",
    "                ans += cnt-1\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
